package bloom_filter

import (
	"github.com/Workiva/go-datastructures/bitarray"
	"github.com/spaolacci/murmur3"
	"math"
	"sync"
)

/*
StandardBloom 标准布隆过滤器
n 欲插入Bloom Filter中的元素数目:
k 哈希的次数(散列函数个数)；
m 布隆过滤器的长度（如比特数组的大小）；
期望误差 ε  (p)
根据计算布隆过滤器最佳长度m(size)
*/
type StandardBloom struct {
	size     uint64
	k        uint64
	rwLock   sync.RWMutex
	bitArray bitarray.BitArray
}

// Add data into standardBloom
func (s *StandardBloom) Add(data []byte) (err error) {

	// set bits in bitarray
	if err = s.set(s.getLocations(data)); err != nil {
		return err
	}
	// get the obj hash
	// s.bitArray.SetBit()
	return nil
}

// Check data in bloom
func (s *StandardBloom) Check(data []byte) bool {

	ok, err := s.getBits(s.getLocations(data))
	if err != nil {
		return false
	}

	return ok
}

func (s *StandardBloom) Reset() {
	s.bitArray.Reset()
}

// getLocations get k hash locations
func (s *StandardBloom) getLocations(data []byte) []uint64 {
	locations := make([]uint64, s.k)
	for i := uint64(0); i < s.k; i++ {
		// 哈希计算,使用的是"MurmurHash3"算法,并每次追加一个固定的i字节进行计算
		hashVal := murmur3.Sum64(append(data, byte(i)))
		// 取下标 offset
		locations[i] = hashVal % s.size
	}
	return locations
}

func (s *StandardBloom) set(locations []uint64) (err error) {
	// set location in bitarray
	s.rwLock.Lock()
	defer s.rwLock.Unlock()

	for _, location := range locations {
		if err = s.bitArray.SetBit(location); err != nil {
			return ErrSetBits
		}
	}

	return nil
}

func (s *StandardBloom) getBits(locations []uint64) (ok bool, err error) {
	s.rwLock.RLock()
	defer s.rwLock.RUnlock()

	for _, location := range locations {
		ok, err = s.bitArray.GetBit(location)
		if err != nil {
			return false, ErrGetBits
		}
		if !ok {
			return false, nil
		}
	}
	return true, nil
}

/*
optimalNumOfHshFunc 计算最优哈希次数

	布隆过滤器的长度（如比特数组的大小）；
	n 欲插入Bloom Filter中的元素数目:
	k = m/n * ln2

return 最优哈希次数 k
*/
func optimalNumOfHashFunc(m, n uint) uint {
	k := math.Ceil((float64(m) / float64(n)) * math.Log(2))
	return uint(k)
}

/*
	optimalSizeOfBits 计算最优数组长度
	n 欲插入Bloom Filter中的元素数目:
	p 期望误差 ε  (p)
	m= (-n * ln P )/(ln2)²

return 布隆过滤器的长度（如比特数组的大小）m
*/
func optimalSizeOfBits(n uint, p float64) uint {
	m := math.Ceil((float64(n) * math.Log(p)) / math.Log(1.0/(math.Pow(2, math.Log2(math.E)))))
	return uint(m)
}

// NewStandardBloom
// size(m) 布隆过滤器的长度（如比特数组的大小）；
// k 哈希的次数(散列函数个数)；
func NewStandardBloom(size, k uint64, args ...bool) BloomFilter {
	return &StandardBloom{
		size:     size,
		k:        k,
		bitArray: bitarray.NewBitArray(size, args...),
		rwLock:   sync.RWMutex{},
	}
}

/*
NewOptimalStandardBloom

	num 欲插入Bloom Filter中的元素数目
	p 期望误差 ε  (p)

return StandardBloom
*/
func NewOptimalStandardBloom(num uint, p float64, args ...bool) BloomFilter {
	size := optimalSizeOfBits(num, p)
	return &StandardBloom{
		size:     uint64(size),
		k:        uint64(optimalNumOfHashFunc(size, num)),
		bitArray: bitarray.NewBitArray(uint64(size), args...),
		rwLock:   sync.RWMutex{},
	}
}
